{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Total Space Wasted With K Resizing Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSpaceWastedKResizing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 次调整数组大小浪费的最小总空间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在设计一个动态数组。给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，其中&nbsp;<code>nums[i]</code>&nbsp;是&nbsp;<code>i</code>&nbsp;时刻数组中的元素数目。除此以外，你还有一个整数 <code>k</code>&nbsp;，表示你可以 <strong>调整</strong>&nbsp;数组大小的 <strong>最多</strong>&nbsp;次数（每次都可以调整成 <strong>任意</strong>&nbsp;大小）。</p>\n",
    "\n",
    "<p><code>t</code>&nbsp;时刻数组的大小&nbsp;<code>size<sub>t</sub></code>&nbsp;必须大于等于&nbsp;<code>nums[t]</code>&nbsp;，因为数组需要有足够的空间容纳所有元素。<code>t</code>&nbsp;时刻 <strong>浪费的空间</strong>&nbsp;为&nbsp;<code>size<sub>t</sub> - nums[t]</code>&nbsp;，<strong>总</strong>&nbsp;浪费空间为满足&nbsp;<code>0 &lt;= t &lt; nums.length</code>&nbsp;的每一个时刻&nbsp;<code>t</code>&nbsp;浪费的空间&nbsp;<strong>之和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>在调整数组大小不超过 <code>k</code>&nbsp;次的前提下，请你返回 <strong>最小总浪费空间</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意：</strong>数组最开始时可以为&nbsp;<strong>任意大小</strong>&nbsp;，且&nbsp;<strong>不计入</strong>&nbsp;调整大小的操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [10,20], k = 0\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>size = [20,20].\n",
    "我们可以让数组初始大小为 20 。\n",
    "总浪费空间为 (20 - 10) + (20 - 20) = 10 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [10,20,30], k = 1\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>size = [20,20,30].\n",
    "我们可以让数组初始大小为 20 ，然后时刻 2 调整大小为 30 。\n",
    "总浪费空间为 (20 - 10) + (20 - 20) + (30 - 30) = 10 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [10,20,15,30,20], k = 2\n",
    "<b>输出：</b>15\n",
    "<b>解释：</b>size = [10,20,20,30,30].\n",
    "我们可以让数组初始大小为 10 ，时刻 1 调整大小为 20 ，时刻 3 调整大小为 30 。\n",
    "总浪费空间为 (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= nums.length - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-total-space-wasted-with-k-resizing-operations](https://leetcode.cn/problems/minimum-total-space-wasted-with-k-resizing-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-total-space-wasted-with-k-resizing-operations](https://leetcode.cn/problems/minimum-total-space-wasted-with-k-resizing-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,20]\\n0', '[10,20,30]\\n1', '[10,20,15,30,20]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        f = [0]\n",
    "        s = [nums[0]]\n",
    "        ma = nums[0]\n",
    "        n = len(nums)\n",
    "        for index in range(1, n):\n",
    "            ma = max(ma, nums[index])\n",
    "            s.append(s[-1] + nums[index])\n",
    "            f.append(ma * (index + 1) - s[-1])\n",
    "        \n",
    "        res = f[-1]\n",
    "        \n",
    "        for i in range(1, k + 1):\n",
    "            g = f[:]\n",
    "            f = []\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if j + 1 <= i:\n",
    "                    f.append(0)\n",
    "                else:\n",
    "                    f.append(g[j - 1])\n",
    "                    ma = nums[j]\n",
    "                    for cut_pos in range(j - 1, i - 1, -1):\n",
    "                        ma = max(nums[cut_pos], ma)\n",
    "                        f[-1] = min(f[-1], g[cut_pos - 1] + ma * (j - cut_pos + 1) - s[j] + s[cut_pos - 1])\n",
    "        \n",
    "            f.reverse()\n",
    "            res = min(res, f[-1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = [[inf] * (k + 2) for _ in range(n + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(i, k + 1) + 1):\n",
    "                # mx = nums[i - 1]\n",
    "                # s = nums[i - 1]\n",
    "                mx = 0\n",
    "                s = 0\n",
    "                for d in range(i, j - 1, -1):\n",
    "                    x = nums[d - 1]\n",
    "                    mx = max(mx, x)\n",
    "                    s += x\n",
    "                    dp[i][j] = min(\n",
    "                        dp[i][j],\n",
    "                        dp[d - 1][j - 1] + (i - d + 1) * mx - s,\n",
    "                    )\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[math.inf for _ in range(k+1)] for _ in range(n)]\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(k+1):\n",
    "                max_val = 0\n",
    "                total_sum = 0\n",
    "                for l in range(i, -1, -1):\n",
    "                    max_val = max(max_val, nums[l])\n",
    "                    total_sum += nums[l]\n",
    "                    waste = max_val * (i - l + 1) - total_sum\n",
    "                    if j > 0 and l > 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[l-1][j-1] + waste)\n",
    "                    elif l == 0 and j == 0:\n",
    "                        dp[i][j] = waste\n",
    "                        \n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        F = [[inf] * n for i in range(k+1)]\n",
    "        acc = list(accumulate(nums))\n",
    "        for i in range(k+1):\n",
    "            mx = 0\n",
    "            for j in range(n):\n",
    "                mx = max(mx,nums[j])\n",
    "                if not i:F[i][j] = mx*(j+1)-acc[j];continue\n",
    "                mx = 0\n",
    "                for m in range(j,i-1,-1):\n",
    "                    mx = max(mx,nums[m])\n",
    "                    F[i][j] = min(F[i][j],mx*(j-m+1)-(acc[j]-acc[m-1])+F[i-1][m-1])\n",
    "        return F[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ma=-inf\n",
    "        cc=0\n",
    "        dp=[[inf]*(k+1) for i in range(n)]\n",
    "        for i,x in enumerate(nums):\n",
    "            ma=max(ma,x)\n",
    "            cc+=x\n",
    "            m=0\n",
    "            c=0\n",
    "            dp[i][0]=(i+1)*ma-cc\n",
    "            for j in range(i,0,-1):\n",
    "                m=max(nums[j],m)\n",
    "                c+=nums[j]\n",
    "                for z in range(1,k+1):\n",
    "                    dp[i][z]=min(dp[i][z],dp[j-1][z-1]+m*(i-j+1)-c) \n",
    "        #print(dp)\n",
    "        return min(dp[-1])\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        dp = [[inf]*(k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        ceil = 0\n",
    "        for i in range(n):\n",
    "            ceil = nums[i] if nums[i] > ceil else ceil\n",
    "            dp[i+1][0] = ceil*(i+1) - pre[i+1]\n",
    "            for j in range(1, k+1):\n",
    "                cur = 0\n",
    "                for x in range(i, -1, -1):\n",
    "                    cur = nums[x] if nums[x] > cur else cur\n",
    "                    val = dp[x][j-1] + cur*(i-x+1) - (pre[i+1] - pre[x])\n",
    "                    if val < dp[i+1][j]:\n",
    "                        dp[i+1][j] = val\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        dp = [[inf]*(k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        ceil = 0\n",
    "        for i in range(n):\n",
    "            ceil = nums[i] if nums[i] > ceil else ceil\n",
    "            dp[i+1][0] = ceil*(i+1) - pre[i+1]\n",
    "            cur = 0\n",
    "            for x in range(i, -1, -1):\n",
    "                cur = nums[x] if nums[x] > cur else cur\n",
    "                for j in range(1, k+1):\n",
    "                    val = dp[x][j-1] + cur*(i-x+1) - (pre[i+1] - pre[x])\n",
    "                    if val < dp[i+1][j]:\n",
    "                        dp[i+1][j] = val\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        k += 1\n",
    "        n = len(nums)\n",
    "\n",
    "        if k>=n:\n",
    "            return 0\n",
    "\n",
    "        # 计算前缀和\n",
    "        presums = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            presums[i+1] = presums[i] + nums[i]\n",
    "\n",
    "        # 计算每一段的权值\n",
    "        weights = [[0]*(n+1) for _ in range(n)]\n",
    "        for i in range(n-1):\n",
    "            mx = nums[i]\n",
    "            for j in range(i+2, n+1):\n",
    "                if nums[j-1] > mx:\n",
    "                    mx = nums[j-1]\n",
    "                weights[i][j] = mx * (j-i) - (presums[j] - presums[i])\n",
    "\n",
    "        dp = [[0]*(k+1) for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][1] = weights[0][i]\n",
    "            for j in range(2, k+1):\n",
    "                dp[i][j] = min([dp[m][j-1] + weights[m][i] for m in range(j-1, i)], default=0)\n",
    "\n",
    "        return dp[n][k]\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ma=-inf\n",
    "        cc=0\n",
    "        dp=[[inf]*(k+1) for i in range(n)]\n",
    "        for i,x in enumerate(nums):\n",
    "            ma=max(ma,x)\n",
    "            cc+=x\n",
    "            m=0\n",
    "            c=0\n",
    "            dp[i][0]=(i+1)*ma-cc\n",
    "            for j in range(i,0,-1):\n",
    "                m=max(nums[j],m)\n",
    "                c+=nums[j]\n",
    "                for z in range(1,k+1):\n",
    "                    dp[i][z]=min(dp[i][z],dp[j-1][z-1]+m*(i-j+1)-c) \n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # 预处理数组 g\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            # 记录子数组的最大值\n",
    "            best = float(\"-inf\")\n",
    "            # 记录子数组的和\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                best = max(best, nums[j])\n",
    "                total += nums[j]\n",
    "                g[i][j] = best * (j - i + 1) - total\n",
    "        \n",
    "        f = [[float(\"inf\")] * (k + 2) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, k + 2):\n",
    "                for i0 in range(i + 1):\n",
    "                    f[i][j] = min(f[i][j], (0 if i0 == 0 else f[i0 - 1][j - 1]) + g[i0][i])\n",
    "\n",
    "        return f[n - 1][k + 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        # 最小浪费空间 也就是将nums分成k+1段 每一段的权值为该段的最大值减去子段和\n",
    "            n = len(nums)\n",
    "            g = [[0 for _ in range(n)] for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                best = -inf\n",
    "                tot = 0\n",
    "                for j in range(i, n):\n",
    "                    best = nums[j] if best < nums[j] else best\n",
    "                    tot += nums[j]\n",
    "                    g[i][j] = best * (j - i + 1) - tot\n",
    "\n",
    "            dp = [[inf for _ in range(k + 2)] for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                for j in range(1, k + 2):\n",
    "                    # 枚举最后一段\n",
    "                    for i0 in range(i + 1):\n",
    "                        cur = (0 if i0 == 0 else dp[i0 - 1][j - 1]) + g[i0][i]\n",
    "                        dp[i][j] = cur if cur < dp[i][j] else dp[i][j]\n",
    "            return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            best = nums[i]\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                best = max(best, nums[j])\n",
    "                total += nums[j]\n",
    "                g[i][j] = best * (j - i + 1) - total\n",
    "        f = [[inf] * (k + 2) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, k + 2):\n",
    "                for i0 in range(i + 1):\n",
    "                    f[i][j] = min(f[i][j], (0 if i0 == 0 else f[i0 - 1][j - 1]) + g[i0][i])\n",
    "        return f[n - 1][k + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "动态规划\n",
    "\n",
    "g[i][j]: nums[i..j] 这一段的最大值乘以这一段的长度再减去这一段的元素和\n",
    "f[i][j]: 将 nums[0:i] 分成 j 段的最小总权值。\n",
    "'''\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 预处理数组 g\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            # 记录子数组的最大值\n",
    "            best = float(\"-inf\")\n",
    "            # 记录子数组的和\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                best = max(best, nums[j])\n",
    "                total += nums[j]\n",
    "                g[i][j] = best * (j - i + 1) - total\n",
    "        \n",
    "        f = [[float(\"inf\")] * (k + 2) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, k + 2):\n",
    "                for i0 in range(i + 1):\n",
    "                    f[i][j] = min(f[i][j], (0 if i0 == 0 else f[i0 - 1][j - 1]) + g[i0][i])\n",
    "\n",
    "        return f[n - 1][k + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # 预处理数组 g\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            # 记录子数组的最大值\n",
    "            best = float(\"-inf\")\n",
    "            # 记录子数组的和\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                best = max(best, nums[j])\n",
    "                total += nums[j]\n",
    "                g[i][j] = best * (j - i + 1) - total\n",
    "        \n",
    "        f = [[float(\"inf\")] * (k + 2) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, k + 2):\n",
    "                for i0 in range(i + 1):\n",
    "                    f[i][j] = min(f[i][j], (0 if i0 == 0 else f[i0 - 1][j - 1]) + g[i0][i])\n",
    "\n",
    "        return f[n - 1][k + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # 预处理数组 g\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            # 记录子数组的最大值\n",
    "            best = float(\"-inf\")\n",
    "            # 记录子数组的和\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                best = max(best, nums[j])\n",
    "                total += nums[j]\n",
    "                g[i][j] = best * (j - i + 1) - total\n",
    "        \n",
    "        f = [[float(\"inf\")] * (k + 2) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, k + 2):\n",
    "                for i0 in range(i + 1):\n",
    "                    f[i][j] = min(f[i][j], (0 if i0 == 0 else f[i0 - 1][j - 1]) + g[i0][i])\n",
    "\n",
    "        return f[n - 1][k + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 将数组划分为k+1个连续的子数组 每个子数组的权值为最大值减去区间和\n",
    "        f = [[inf for _ in range(k + 2)] for _ in range(n)]\n",
    "        g = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            best = -inf\n",
    "            tot = 0\n",
    "            for j in range(i, n):\n",
    "                best = best if best > nums[j] else nums[j]\n",
    "                tot += nums[j]\n",
    "                g[i][j] = best * (j - i + 1) - tot\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1, k + 2):\n",
    "                for i0 in range(i + 1):\n",
    "                    cur = (0 if i0 == 0 else f[i0-1][j-1]) + g[i0][i]\n",
    "                    f[i][j] = cur if cur < f[i][j] else f[i][j]\n",
    "        return f[-1][-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        # 最小浪费空间 也就是将nums分成k+1段 每一段的权值为该段的最大值减去子段和\n",
    "            n = len(nums)\n",
    "            g = [[0 for _ in range(n)] for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                best = -inf\n",
    "                tot = 0\n",
    "                for j in range(i, n):\n",
    "                    best = nums[j] if best < nums[j] else best\n",
    "                    tot += nums[j]\n",
    "                    g[i][j] = best * (j - i + 1) - tot\n",
    "\n",
    "            dp = [[0x3f3f3f3f for _ in range(k + 2)] for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                for j in range(1, k + 2):\n",
    "                    # 枚举最后一段\n",
    "                    for i0 in range(i + 1):\n",
    "                        cur = (0 if i0 == 0 else dp[i0 - 1][j - 1]) + g[i0][i]\n",
    "                        dp[i][j] = cur if cur < dp[i][j] else dp[i][j]\n",
    "            return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(itertools.accumulate(nums, initial=0))\n",
    "        mx = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            mx[i+1] = max(mx[i], nums[i])\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if j >= i:\n",
    "                return 0\n",
    "            if j == 0:\n",
    "                return mx[i+1] * (i+1) - pre[i+1]\n",
    "            ans = math.inf\n",
    "            s = x = 0\n",
    "            for p in range(i, j-1, -1):\n",
    "                s += nums[p]\n",
    "                x = max(x, nums[p])\n",
    "                ans = min(ans, f(p-1, j-1) + x * (i-p+1) - s)\n",
    "            return ans\n",
    "        \n",
    "        return f(n-1, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dfs 贪心，肯定是k个板子全插入最好\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        tot = sum(nums)\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, pre): # 表示的是 nums[pre:] 中 还可以插入 k 块板子的时候，最小差\n",
    "            if cur == 0:\n",
    "                h = max(nums[pre:], default=0)\n",
    "                return h*(n - pre)\n",
    "\n",
    "            ans = float('inf')\n",
    "            h = nums[pre]\n",
    "            for j in range(pre+1, min(n - cur + 2, n)): # 遍历下一块板子的起始位置\n",
    "                ans = min(dfs(cur-1, j) + (j - pre)*h, ans)\n",
    "                h = max(h, nums[j])\n",
    "            return ans\n",
    "\n",
    "        return dfs(k, 0) - tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, left):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            if not left:\n",
    "                m = max(nums[idx:])\n",
    "                return m * (n - idx)\n",
    "            m = 0\n",
    "            ans = inf\n",
    "            for i in range(idx, n - left):\n",
    "                m = max(m, nums[i])\n",
    "                ans = min(ans, dfs(i+1, left - 1) + m * (i+1 - idx))\n",
    "            return ans\n",
    "        return dfs(0, k) - sum(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, left):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            if not left:\n",
    "                m = max(nums[idx:])\n",
    "                return m * (n - idx)\n",
    "            m = 0\n",
    "            ans = inf\n",
    "            for i in range(idx, n - left):\n",
    "                m = max(m, nums[i])\n",
    "                ans = min(ans, dfs(i+1, left - 1) + m * (i+1 - idx))\n",
    "            return ans\n",
    "        return dfs(0, k) - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(itertools.accumulate(nums, initial=0))\n",
    "        mx = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            mx[i+1] = max(mx[i], nums[i])\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if j >= i:\n",
    "                return 0\n",
    "            if j == 0:\n",
    "                return mx[i+1] * (i+1) - pre[i+1]\n",
    "            ans = math.inf\n",
    "            s = x = 0\n",
    "            for p in range(i, -1, -1):\n",
    "                s += nums[p]\n",
    "                x = max(x, nums[p])\n",
    "                ans = min(ans, f(p-1, j-1) + x * (i-p+1) - s)\n",
    "            return ans\n",
    "        \n",
    "        return f(n-1, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        # 预处理一下可能能够快一点\n",
    "        n = len(nums)\n",
    "        p = list(accumulate(nums, initial=0))\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ma = nums[i]\n",
    "            for j in range(i, n):\n",
    "                dp[i][j] = ma = max(ma, nums[j])\n",
    "        \n",
    "        @cache\n",
    "        def f(i, k):\n",
    "            if k < 0:\n",
    "                return inf\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for j in range(i, n):\n",
    "                ans = min(ans,  dp[i][j] * (j-i+1) - (p[j+1]-p[i]) + f(j+1, k-1))\n",
    "            return ans\n",
    "    \n",
    "        return f(0, k+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        k += 1\n",
    "        mx = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i, n):\n",
    "                tmp = max(tmp, nums[j])\n",
    "                mx[i][j] = tmp \n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        ans = inf \n",
    "\n",
    "        @cache \n",
    "        def f(i, rest):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if rest == 1:\n",
    "                return mx[i][n - 1] * (n - i) - acc[-1] + acc[i]\n",
    "            res = inf \n",
    "            for j in range(i, n):\n",
    "                res = min(res, f(j + 1, rest - 1) + mx[i][j] * (j - i + 1) - acc[j + 1] + acc[i])\n",
    "            return res \n",
    "        \n",
    "        return f(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            mx = nums[i]\n",
    "            sm = 0\n",
    "            for j in range(i, n):\n",
    "                mx = max(mx, nums[j])\n",
    "                sm += nums[j]\n",
    "                dp[i][j] = mx * (j - i + 1) - sm\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j < 0:\n",
    "                return float('inf')\n",
    "            if n - i <= j:\n",
    "                return 0\n",
    "            return min(dp[i][k] + dfs(k + 1, j - 1) for k in range(i, n))\n",
    "        \n",
    "        return dfs(0, k+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n:\n",
    "             return 0\n",
    "          if j == k:\n",
    "             return arr[i][n - 1]\n",
    "          res = inf\n",
    "          for x in range(i, n):\n",
    "             res = min(res, dfs(x + 1, j + 1) + arr[i][x])\n",
    "          return res\n",
    "\n",
    "       n = len(nums)\n",
    "       arr = [[0] * n for _ in range(n)]\n",
    "       s = 0\n",
    "       for i in range(n):\n",
    "          s += nums[i]\n",
    "          m = nums[i]\n",
    "          for j in range(i, n):\n",
    "             m = max(m, nums[j])\n",
    "             arr[i][j] = m * (j - i + 1)\n",
    "       return dfs(0, 0) - s"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
